#include <bits/stdc++.h>
#include <vector>

using namespace std;

/**
 * 689. 三个无重叠子数组的最大和
已解答
困难
相关标签
相关企业
给你一个整数数组 nums 和一个整数 k ，找出三个长度为 k 、互不重叠、且全部数字和最大的子数组，并返回这三个子数组。

以下标的数组形式返回结果，数组中的每一项分别指示每个子数组的起始位置（下标从 0 开始）。如果有多个结果，返回字典序最小的一个。

 

示例 1：

输入：nums = [1,2,1,2,6,7,5,1], k = 2
输出：[0,3,5]
解释：子数组 [1, 2], [2, 6], [7, 5] 对应的起始下标为 [0, 3, 5]。
也可以取 [2, 1], 但是结果 [1, 3, 5] 在字典序上更小。
示例 2：

输入：nums = [1,2,1,2,1,2,1,2,1], k = 2
输出：[0,2,4]
 

提示：

1 <= nums.length <= 2 * 104
1 <= nums[i] < 216
1 <= k <= floor(nums.length / 3)
 */

// 法一
class Solution {
    public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        
        // sum[i] 记录从i开始的长度为k的子数组的和
        vector<int> sum(n - k + 1);
        for (int i = 0; i < k; ++i) {
            sum[0] += nums[i];  // 初始化第一个子数组的和
        }

        // 计算每个长度为 k 的子数组的和
        for (int i = 1; i < sum.size(); ++i) {
            sum[i] = sum[i - 1] - nums[i - 1] + nums[i + k - 1];  // 滑动窗口更新
        }

        // left[i] 存储在 [0, i] 范围内和最大的子数组的起始位置
        vector<int> left(n - k + 1);
        left[0] = 0;
        for (int i = 1; i < left.size(); ++i) {
            left[i] = (sum[i] > sum[left[i - 1]]) ? i : left[i - 1];  // 如果当前和更大，更新左侧
        }

        // right[i] 存储在 [i, n - 1] 范围内和最大的子数组的起始位置
        vector<int> right(n - k + 1);
        right[right.size() - 1] = right.size() - 1;
        for (int i = right.size() - 2; i >= 0; --i) {
            right[i] = (sum[i] >= sum[right[i + 1]]) ? i : right[i + 1];  // 如果当前和更大，更新右侧
        }

        // 寻找最大和的三元组
        int maxSum = 0;
        vector<int> ans(3);
        // 遍历中间的子数组
        for (int j = k; j < sum.size() - k; ++j) {
            int i = left[j - k];    // 第一个子数组的起始位置
            int r = right[j + k];   // 第三个子数组的起始位置
            int cur = sum[i] + sum[j] + sum[r];  // 当前三个子数组的和
            if (cur > maxSum) {
                maxSum = cur;
                ans = {i, j, r};
            }
        }

        return ans;
    }
};
    
// 法二
class Solution {
    public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> sums( n, 0 );
        //sums[i] 表示以i位置开头的，长度为k的子数组的累加和
        for ( int l = 0, r = 0, sum = 0; r < n; r++ ) {
            sum += nums[r];
            if ( r - l + 1 == k ) {
                sums[l] = sum;
                sum -= nums[l];
                l++;
            }
        }

        vector<int> prefix( n, 0 );
        //prefix[i]表示 0...i位置，长度为k的最大累加和 的子数组的开头下标
        prefix[k - 1] = 0;//只有从k - 1开始，才有长度为k的子数组
        for ( int l = 1, r = k; r < n; r++, l++ ) {
            // 长度prefix[k - 1] 以及把之前子数组累加和的情况都考虑了
            //所以prefix[k] 只要考虑 只存在 下标包括k的子数组情况 与之前prefix[k - 1] 的最大累加和比较即可  
            if ( sums[l] > sums[prefix[r - 1] ] ) {
                prefix[r] = l;
            } else {
                prefix[r] = prefix[r - 1];
            }
        }

        vector<int> suffix( n, 0 );//后缀处理，同理于prefix
        // prefix[i]表示 i....n - 1位置，长度为k的最大累加和 的子数组的开头下标
        suffix[n - k] = n -k; //开始出现k长度的子数组的开头下标
        for ( int l = n - k - 1; l >= 0; l-- ) {
            if ( sums[l] >= sums[suffix[l + 1] ] ) {
                suffix[l] = l;
            } else {
                suffix[l] = suffix[l + 1];
            }
        }

        int a = -1, b = -1, c = -1, ans = INT_MIN, sum = 0;
        for ( int i = k, j = 2*k - 1; j < n - k; i++, j++ ) {
            int p = prefix[i - 1];
            int s = suffix[j + 1];
            sum = sums[p] + sums[i] + sums[s];
            if ( sum > ans ) {
                a = p;
                b = i;
                c = s;
                ans = sum;
            }
        }

        return { a, b ,c };
    }
};
